//
//  216. 组合总和III.swift
//  LeetCodeTrain
//
//  Created by rjb on 2021/6/27.
//  Copyright © 2021 rjb. All rights reserved.
//

import Foundation
class Solution216 {
    // 在1-9的数组中，找出和为n的k个数。
    // 这个实际上时一个组合的问题
    var result: [[Int]] = []
    var path: [Int] = []
    func combinationSum3(_ k: Int, _ n: Int) -> [[Int]] {
        backTrace(target: n, k: k, start: 1)
        return result
    }
    func backTrace(target: Int, k: Int, start: Int) {
        if target == 0 && k == 0{
            result.append(path)
            return
        }
        if start > 9 {
            return
        }
        for i in start...9 where k > 0 && target - i >= 0 {
            path.append(i)
            backTrace(target: target - i, k: k - 1, start: i + 1)
            path.removeLast()
        }
    }
    static func test() {
        let solution = Solution216()
        //        [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
        let k = 3, n = 9
        let result = solution.combinationSum3(k, n)
        print(result)
    }
}
